package com.xy6.algo.dynamic;


/**
 * 最长公共子序列
 * <pre>
 * LCS问题，应用：论文查重、文本对比工具（beyond compare）
 * 
 * 北大POJ1458
 * 给出两个字符串，求出这样的一个最长的公共子序列的长度：
 * 子序列中的每个字符都能在两个原串中找到， 而且每个字符的先后顺序和原串中的先后顺序一致。
 * 
 * 性能：时间效率：O(m*n)，空间效率：m*n + m + C
 * 
 * 假设：两个字符串为s1, s2；遍历s1中字符，索引为i；遍历s2中字符，索引为j
 * 状态转换方程：
 * maxlen(i,j) = 
 * maxlen(i-1, j-1) + 1,  (s1[i] = s2[j])
 * max(maxlen(i, j-1), maxlen(i-1, j)),  (s1[i] != s2[j])
 * 
 * 创建一个二维数组len[m][n]，初始值都为0，保存s1前i个字符与s2前n个字符的最长公共序列；
 * 遍历s1中字符，索引为i；
 * 遍历s2中字符，索引为j；
 * 比较s1[i]是否等于s2[j]，如果相等，则len[i][j] = len[i-1][j-1] + 1；
 * 如果不等，len[i][j] = max(len[i],[j-1], len[i-1][j])；
 * 遍历直至j等于n；
 * 遍历直至i等于m，遍历终止，len[m-1][n-1]即两个字符串最长公共子序列的长度；
 * 
 * 优化：由于只求最大值，将二维数组len[m][n]改为一维数组len[n]；
 * 状态转换方程：
 * maxlen(j) = 
 * maxlen(j-1) + 1,  (s1[i] = s2[j])
 * max(maxlen(j-1), maxlen(j)),  (s1[i] != s2[j])
 * 
 * </pre>
 * 
 * @author zhang
 * @since 2017-11-03
 */
public class LCS {

	/**
	 * 求两个字符串的最长公共子序列，计算其长度
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static int calc(String s1, String s2){
		int m = s1.length();
		int n = s2.length();
		int[] len = new int[n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(s1.charAt(i) == s2.charAt(j)){
					len[j] = len(len, j-1) + 1;
				} else {
					len[j] = max(len(len, j), len(len, j-1));
				}
			}
		}
		
		return len[n-1];
	}
	
	/**
	 * 获取二维数组中某一索引元素
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	private static int len(int[] len, int i){
		if(i < 0 || i >= len.length){
			return 0;
		}
		return len[i];
	}
	
	/**
	 * 获取两个元素中的较大值
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	private static int max(int i, int j){
		return i > j ? i : j;
	}
	
}
